# -*- coding: utf-8 -*-
# Created by zhangyanqi on 2018/4/27

"""
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

思路：
此题不仅要层序遍历，还需要判断层数
"""


# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x, l, r):
        self.val = x
        self.left = l
        self.right = r


class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        # 返回结果
        result = []
        # 每层的内容
        temp = []
        # 每层总数
        count = 0
        # 层
        tier = 1
        l = [root]
        while len(l) != 0:
            # 取出
            root = l.pop(0)
            count += 1
            # 判断队列中是否全部都是none，如果是,将上一层的结果放入结果集中，终止
            if root is None:
                is_all_none = True
                for i in l:
                    if i is not None:
                        is_all_none = False
                        break
                if is_all_none:
                    if len(temp) != 0:
                        result.append(temp)
                    return result
                l.append(None)
                l.append(None)
                if count == 2 ** (tier - 1):
                    result.append(temp)
                    temp = []
                    tier += 1
                    count = 0
                continue
            temp.append(root.val)
            if count == 2 ** (tier - 1):
                result.append(temp)
                temp = []
                tier += 1
                count = 0
            if root.left is not None:
                l.append(root.left)
            else:
                l.append(None)
            if root.right is not None:
                l.append(root.right)
            else:
                l.append(None)
        return result


if __name__ == "__main__":
    node5 = TreeNode(5, None, None)
    node4 = TreeNode(4, node5, None)
    node3 = TreeNode(3, node4, None)
    node2 = TreeNode(2, node3, None)
    node1 = TreeNode(1, node2, None)

    s = Solution()
    depth = s.levelOrder(node1)
    print(depth)
